\section{Experiments}
\label{experiments}
In this section, we empirically evaluate our path-tree cover approach both real and synthetic datasets. 
We are particularly interested in the following three questions:
\benum 
\item For path-tree cover approach, what is its compression rate compared with optimal tree-cover approach? 
\item What is path-tree's construction time and query time compared with existing approaches?
\eenum 

All tests were run on an AMD Opteron 2.0GHz machine with 2GB of main memory, running Linux (Fedora Core 4), with a 2.6.17 x86\_64 kernel.  
All algorithms are implemented in C++. 
Table~\ref{datasets} shows the real graphs. 
Among them, AgroCyc, Anthra, Ecoo157, HpyCyc, Human,Mtbra, and VchoCyc are from EcoCyc~\footnote{http://ecocyc.org/}; Xmark and Nasa are XML documents; and
Reactome, aMaze, and KEGG are metabolic networks  provided by Tri{\ss}l ~\cite{Trissl07}. The first two columns are the number of vertices and edges in the original graphs and the last columns are the number of vertices and edges in the DAG after compressing the strongly connected components. 
\input{Figures/Datasets.tex}

\input{Figures/RealDataPathTree.tex}




We measure the compressed transitive closure size which is the total number of vertices each vertex in DAG has to record, and query time and the index construction time for three different type of methods: Tree corresponding to the optimal tree cover approach by Agrawal~\cite{SIGMOD:AgrawalBJ:1989}, Ptree-1 corresponding to the path-tree approach utilizing optimal tree cover together with {\em OptIndex} (Subsection~\ref{OPTC}), 
Ptree-2 corresponding to the path tree approach described in Section~\ref{pathtree} and utilizing the {\em MinPathIndex} criteria. 
In addition, a query is generated by randomly picking a pair of nodes for reachability test. 
We measure the query time by answering a total of $100,000$ randomly generated reachability queries. 

\paragraph*{Real Life Graphs}
Table~\ref{realdatapathtree} shows the compressed transitive closure size, the construction time, and the query time. 
We can see that PTree-1 consistently has better compression rate than the tree approaches, which confirms our theoretical analysis in Subsection~\ref{OPTC}. 
PTree-2 in $9$ out of $12$ datasets perform much better than the optimal tree cover approach. 
Overall, Ptree-1 and Ptree-2 achieve an average of $10$ times and $3$ times better compression rate compared with the optimal tree cover approach. 
The compressed transitive closure size directly affects the query time for the reachability queries. This can be also observed in the query time results (Ptree-1 and Ptree-2 are $30\%$ and $10\%$ faster than the optimal tree cover approach for answering the reachability query). 

For the construction time, we do expect Ptree-1 to be slower than the optimal tree cover approach since it is using that as the first step for path-decomposition (Recall that we extract the paths from the optimal tree). 
Interestingly, we found that optimal tree construction actually performs faster than the PTree-2 approach even though it has to find all the predecessor sets (which is equivalent to the transitive closure computation) first. 
Our further analysis shows that even each step in in PTree-2 only has linear cost. But a lot of memory read and write operations need to be performed, and significantly slow the construction time of the path-tree approaches. 

\paragraph*{Random DAG}
We also compare path-tree approaches with the tree cover approach on the synthetic DAGs. 
Here, we generate a random DAG with fixed edge density to be $2$ and we vary the number of vertices from $10,000$ to $100,000$. 
Figure~\ref{figure:random1} shows the compressed transitive closure size of the path-tree approaches (Ptree-1 and Ptree-2) and optimal tree cover approach (Tree). 
Overall, the compressed transitive closure size of Ptree-1 and Ptree-2 is $1\/3$ to $1\/4$ of the one from the optimal tree cover. 
In the figure, both path-tree approaches perform significantly better than the tree cover approach. 
Figure~\ref{figure:random1} shows the query running time of these three approaches. 

\begin{figure}
\centering
\begin{tabular}{c}
\psfig{figure=Figures/TCrandom.epsi,width=3in,height=2in}
\end {tabular}
%\caption {Path-Decomposition for a DAG}
\label{figure:random1}
\end{figure}


\begin{figure}
\centering
\begin{tabular}{c}
\psfig{figure=Figures/RunningTimerandom.epsi,width=3in,height=2in}
\end {tabular}
%\caption {Path-Decomposition for a DAG}
\label{figure:random2}
\end{figure}

